//最小覆盖子串；
//实例1:
//输入：s="ADOBECODEBANC",t="ABC"
//输出："BANC"
//实例2：
//输入：s="a",t="a"
//输出:"a"
//实例3：
//输入：s="a",t="aa";
//输出："";
public class NM1 {
    public static String fun(String ss,String tt){
        //1.将输入的字符串转换成字符数组；
        char[] s=ss.toCharArray();
        char[] t=tt.toCharArray();
        //2.进行记录t字符数组中有哪些有效字符以及个数；
        int kinds=0;//有效字符的个数；
        int[] hash1=new int[128];
        for(char ch:t){
            if(hash1[ch]++==0){
                kinds++;
            }
        }
        //3.进行关于滑动窗口中相关变量的设置；
        int minLen=Integer.MAX_VALUE;//滑动窗口大小的设置；
        int[] hash2=new int[128];//滑动窗口中字符的记录；
        int begin=-1;//窗口的起始位置；
        //4.开始进行滑动窗口；
        for(int left=0,right=0,count=0;right<s.length;right++){
            //①：进窗口+维护窗口（进窗口后进行维护count）；
            char in=s[right];
            if(++hash2[in]==hash1[in]){
                count++;
            }
            //②：进行判断何时出窗口；
            while(count==kinds){
                if(right-left+1<minLen){
                    minLen=right-left+1;
                    begin=left;
                }
                //③：出窗口+维护count(出窗口前，进行维护窗口）；
                char out=s[left];
                left++;
                if(hash2[out]--==hash1[out]){
                    count--;
                }
            }
        }
        //5.进行结果的更新；
        if(begin==-1){
            return new String();
        }else{
            return ss.substring(begin,begin+minLen);
        }

    }
    public static void main(String[] args){
        String ss="ADOBECODEBANC";
        String tt="ABC";
        String ret=fun(ss,tt);
        System.out.println(ret);
    }
}
